package com.liufei.class05;

// 测试链接：https://leetcode.com/problems/divide-two-integers
public class Code03_BitAddMinusMultiDiv {

    public static int add(int a, int b) {
        int sum = a; // 这里让其等于a，如果b是0，则直接返回a
        while (b != 0) {
            sum = a ^ b; // ^ 可以理解为无进位相加
            b = (a & b) << 1;  // 得到的是进位信息
            a = sum;
        }
        return sum;
    }

    // 求一个数的相反数
    // -b => ~b + 1
    public static int negNum(int num) {
        return add(~num, 1);
    }

    // a + b => a + (-b) => a + (~b + 1)
    // 因为不能出现+，所以a + (~b + 1)这里的加号，全部使用add方法
    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    // 乘法
    public static int multi(int a, int b) {
        int ans = 0;
        while (b != 0) {
            // 说明b的最后一位是1
            if ((b & 1) != 0) {
                ans = add(ans, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return ans;
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }

    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        // x 和 y 必须都是正数
        int res = 0;
        // 这里从30位开始，因为x和y都是正数，31位都是0，移动31位后也是0，是最小的，所以这里就可以忽略
        for (int i = 30; i >= 0 ; i = minus(i, 1)) {
            // x 右移 i位 和 y 左移动 i位都可以，那这里为什么选择右移呢？
            // 因为左移有风险，左移可能移动到最高位，会导致数据有误
            if ((x >> i) >= y) {
                // 将i位设置位1
                res |= (1 << i);
                x = minus(x, y << i);
            }
        }
        // 使用异或。相同位0，不同位1。0对应false，1对应true
        // 如果 a 和 b 符号相同，则返回0，false
        // 如果 a 和 b 符号不同，则返回1，true
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    public static int divide(int a, int b) {
        // 我们知道，Java中Integer.MIN_VALUE的最小值，还是它自己，所以对于最小值转绝对值的情况分类讨论处理，不能直接调用div方法
        // div方法，只适用 a 和 b 大于 Integer.MIN_VALUE 的情况

        // 1. 如果 a 和 b 都是 Integer.MIN_VALUE，两个相等，相除返回1
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            // 2. 如果只有b是Integer.MIN_VALUE，一个数除以系统最小值，返回0
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            // a是最小值，除以 -1，正常是等于a的绝对值，但是这样超过int的取值范围了
            // java中这种情况返回的是系统最大值
            if (b == -1) {
                return Integer.MAX_VALUE;
            }
            // a + b = ？转换位
            // (a + 1) / b = c
            // a - (c * b) = d
            // d / b = e
            // 结果就是 c + e
            int c = div(add(a, 1), b);
            int d = minus(a, multi(c, b));
            int e = div(d, b);
            return add(c, e);
        } else {
            // a 和 b 都不是 Integer.MIN_VALUE
            return div(a, b);
        }
    }

    public static void main(String[] args) {
        int a = Integer.MIN_VALUE;
        int b = -2;
        System.out.println(add(a, b));
        System.out.println(minus(a, b));
        System.out.println(multi(a, b));
        System.out.println(divide(a, b));
        System.out.println(a / b);
    }
}
